from typing import List


class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        length = len(nums)
        result = nums[0] + nums[1] + nums[2]
        for i in range(length):
            j = i + 1
            k = length - 1
            while j < k:
                sum = nums[i] + nums[j] + nums[k]
                if sum == target:
                    return sum

                if abs(sum - target) < abs(result - target):
                    result = sum

                if sum > target:
                    k -= 1
                else:
                    j+=1
        return result


if __name__ == "__main__":
    nums = [-1, 2, 1, -4]
    target = 1
    r = Solution().threeSumClosest(nums, target)
    print(r)

    nums = [1,2,4,8,16,32,64,128]
    target = 82
    r = Solution().threeSumClosest(nums, target)
    print(r)

